"""
解题思路

在这到题目中，我们首先需要证明一点，即什么情况下是无解什么情况下有解。

通过简单的数学证明我们可以得知，

1. 当gas之和小于cost之和该题无解。
2. 而当gas之和不小于cost之和，此题必有解。

那么如何证明第2点呢？很简单，由于gas之和不小于cost之和，所以前N项的前缀和为最小值时，
那么后面的元素之和减去前N项的前缀和还会大于等于0。并且我们找到前N项的前缀和为最小值，
就可以保证后续的gas-cost的累计值一定大于0，并且结余下来的值肯定不小于前N项的前缀和，
故题目必有解。

"""


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        curr_sum, surr_min_index, surr_min = 0, 0, float('inf')
        for i in range(len(gas)):
            curr_sum += gas[i] - cost[i]
            if curr_sum <= surr_min:
                surr_min = curr_sum
                surr_min_index = i
        return (surr_min_index + 1) % len(gas)